package newcoder_exp.justPractise;
import java.util.*;
import org.junit.*;
public class Pra2_LeastCalcTimes {
    
    //矩阵连乘
    
    /* 
        nums:每个矩阵的维度排列
        @return: 选择的分割点
     */
    public int[] matrixChain(int[] nums) {
        int n = nums.length - 1;

        //f[i][j]表示Ai*...*Aj的最少乘法次数
        int[][] f = new int[n + 1][n + 1];
        int[][] s = new int[n + 1][n + 1];
        int t;

        for (int i = 0; i <= n; i++) {
            f[i][i] = 0;
        }

        /* 
            依赖是从下至上的
        */
        for (int j = 2; j <= n; j++) {
            for (int i = j - 1; i >= 1; i--) {
                f[i][j] = Integer.MAX_VALUE;
                //搜索插入点
                for (int k = i; k < j; k++) {
                    t = f[i][k] + f[k + 1][j] + nums[i - 1] * nums[k] * nums[j];
                    if (t < f[i][j]) {
                        f[i][j] = t;
                        s[i][j] = k;
                    }
                }    
            }
        }
        System.out.println(Arrays.deepToString(f));
        System.out.println(Arrays.deepToString(s));

        find(1, n, s);
        return res.stream().mapToInt(Integer::valueOf).toArray();
    }
    List<Integer> res = new ArrayList<>();
    public void find(int i, int j, int[][] s) {
        if (i == j) {
            return;
        }
        int mid = s[i][j];
        find(i, mid, s);
        find(mid + 1, j, s);
        res.add(mid);
        System.out.print("当前执行从" + (i) + "到" + j + "部分的矩阵乘法，");
        System.out.print("：前半部分到" + mid + ", 进行");
        System.out.print("矩阵A[" + (i) + "," + (mid) + "]乘以矩阵" + "矩阵A[" + (mid + 1) + "," + (j) + "]\n");
        System.out.println();
    }

    @Test
    public void test() {
        int[] nums = new int[]{30,35,15,5,10,20,25};
        System.out.println(Arrays.toString(matrixChain(nums)));
    }
}
